{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Dice Roll Simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dieSimulator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #掷骰子模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。</p>\n",
    "\n",
    "<p>不过我们在使用它时有个约束，就是使得投掷骰子时，<strong>连续</strong> 掷出数字&nbsp;<code>i</code>&nbsp;的次数不能超过&nbsp;<code>rollMax[i]</code>（<code>i</code>&nbsp;从 1 开始编号）。</p>\n",
    "\n",
    "<p>现在，给你一个整数数组&nbsp;<code>rollMax</code>&nbsp;和一个整数&nbsp;<code>n</code>，请你来计算掷&nbsp;<code>n</code>&nbsp;次骰子可得到的不同点数序列的数量。</p>\n",
    "\n",
    "<p>假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 <strong>模&nbsp;<code>10^9 + 7</code></strong>&nbsp;之后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, rollMax = [1,1,2,2,2,3]\n",
    "<strong>输出：</strong>34\n",
    "<strong>解释：</strong>我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, rollMax = [1,1,1,1,1,1]\n",
    "<strong>输出：</strong>30\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, rollMax = [1,1,1,2,2,3]\n",
    "<strong>输出：</strong>181\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 5000</code></li>\n",
    "\t<li><code>rollMax.length == 6</code></li>\n",
    "\t<li><code>1 &lt;= rollMax[i] &lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [dice-roll-simulation](https://leetcode.cn/problems/dice-roll-simulation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [dice-roll-simulation](https://leetcode.cn/problems/dice-roll-simulation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[1,1,2,2,2,3]', '2\\n[1,1,1,1,1,1]', '3\\n[1,1,1,2,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        M = 10**9+7\n",
    "          # dp[i][j] represents answer for rolling i times and the last face is j.\n",
    "        dp = [[0 for _ in range(6)] for i in range(n+1)]\n",
    "        \n",
    "        for j in range(6):\n",
    "            dp[1][j] = 1\n",
    "            \n",
    "        for i in range(2, n+1):\n",
    "            for j in range(6):\n",
    "                k = i - rollMax[j]\n",
    "                dp[i][j] = sum(dp[i-1]) % M\n",
    "                # Eliminate results that have rollMax[j] trailing j's. \n",
    "                if k == 1:\n",
    "                    dp[i][j] -= 1\n",
    "                elif k > 1:\n",
    "                    dp[i][j] -= sum(dp[k-1]) % M - dp[k-1][j]\n",
    "                    \n",
    "        return sum(dp[-1]) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        rm = max(rollMax)\n",
    "        dp = [[0]*rm for _ in range(6)]\n",
    "        # print(dp)\n",
    "        for j in range(6):\n",
    "            dp[j][0] = 1\n",
    "        # print(dp)\n",
    "        for i in range(1, n):\n",
    "            next_dp = [[0]*rm for _ in range(6)]\n",
    "            for j in range(6):\n",
    "                for h in range(6):\n",
    "                    for k in range(rollMax[h]):\n",
    "                        if h!=j:\n",
    "                            next_dp[j][0] += dp[h][k]\n",
    "                            next_dp[j][0] %= mod\n",
    "            # print(i, next_dp)\n",
    "            for j in range(6):\n",
    "                for k in range(1, rollMax[j]):\n",
    "                    next_dp[j][k] += dp[j][k-1]\n",
    "                    next_dp[j][k] %= mod\n",
    "            dp = next_dp\n",
    "        #     print(i, dp)\n",
    "        # print(dp)\n",
    "        return sum([sum(dp[i])%mod for i in range(6)])%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        def dp_mark(c=0):\n",
    "            dp=[]\n",
    "            for i in rollMax:\n",
    "                dp.append([0]*i)\n",
    "            if c==1:\n",
    "                for i in dp:\n",
    "                    i[0]=1\n",
    "            return dp\n",
    "        dp=dp_mark(1)\n",
    "        li=[1,1,1,1,1,1]\n",
    "        mod=10**9+7\n",
    "        for i in range(2,n+1):\n",
    "            ndp=dp_mark()\n",
    "            nl=[0]*6\n",
    "            for x in range(6):\n",
    "                _sum=0\n",
    "                for xx in range(6):\n",
    "                    if x==xx:\n",
    "                        continue\n",
    "                    _sum=(_sum+li[xx])%mod\n",
    "                _sumlei=0\n",
    "                for y in range(rollMax[x]):\n",
    "                    if y==0:\n",
    "                        ndp[x][y]=_sum\n",
    "                    else:\n",
    "                        ndp[x][y]=dp[x][y-1]\n",
    "                    _sumlei=(_sumlei+dp[x][y])%mod\n",
    "                nl[x]=sum(ndp[x])%mod\n",
    "            dp=ndp\n",
    "            li=nl\n",
    "            #print(dp)\n",
    "        res=0\n",
    "        for i in dp:\n",
    "            res=(sum(i)+res)%mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        k = sum(rollMax)\n",
    "        dp = [0]*k\n",
    "        start = []\n",
    "        end = [0]\n",
    "        for x in rollMax:\n",
    "            start.append(end[-1])\n",
    "            end.append(start[-1]+x)\n",
    "        end = end[1:]\n",
    "        # print(start,end)\n",
    "        for i in start:\n",
    "            dp[i]=1\n",
    "        for _ in range(1,n):\n",
    "            new_dp = [0]*k\n",
    "            for i in range(6):\n",
    "                s = start[i]\n",
    "                e = end[i]\n",
    "                new_dp[s] = (sum(dp[:s])%MOD+sum(dp[e:])%MOD)%MOD\n",
    "                for j in range(s+1, e):\n",
    "                    new_dp[j] =  dp[j-1]\n",
    "            dp = new_dp\n",
    "        return sum(dp)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        memo = [[0]*16 for _ in range(6)]\n",
    "        for i in range(6):\n",
    "            memo[i][0] = 1\n",
    "        for i in range(n):\n",
    "            next_memo = [[0]*16 for _ in range(6)]\n",
    "            for o in range(6):\n",
    "                for p in range(rollMax[o]+1):\n",
    "                    if p != rollMax[o]:\n",
    "                        next_memo[o][p+1] += memo[o][p]\n",
    "                        next_memo[o][p+1] %= MOD\n",
    "                    if p > 0:\n",
    "                        for q in range(6):\n",
    "                            if o != q:\n",
    "                                next_memo[q][1] += memo[o][p]\n",
    "                                next_memo[q][1] %= MOD\n",
    "            memo = next_memo\n",
    "        return sum((sum(x) % MOD for x in memo)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        dp = [[1] + [0] * (mx-1) for mx in rollMax]\n",
    "        sum_each = [1] * 6\n",
    "        sum_tot = 6\n",
    "        for _ in range(n-1):\n",
    "            for i, mx in enumerate(rollMax):\n",
    "                for k in range(mx-1, 0, -1):\n",
    "                    dp[i][k] = dp[i][k-1]\n",
    "                dp[i][0] = sum_tot - sum_each[i]\n",
    "                sum_each[i] = sum(dp[i]) % MOD\n",
    "            sum_tot = sum(sum_each) % MOD\n",
    "        return sum_tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        M = 1e9 + 7\n",
    "        self.pre_sum = [rollMax[0]] * 6\n",
    "        for num in range(1, 6):\n",
    "            self.pre_sum[num] = self.pre_sum[num - 1] + rollMax[num]\n",
    "\n",
    "        dp = [0] * self.pre_sum[-1]\n",
    "        for i_n in range(n):\n",
    "            dp_tmp = [0] * self.pre_sum[-1]\n",
    "            for j_num in range(6):\n",
    "                if i_n == 0:\n",
    "                    dp_tmp[self.get_pre_sum_idx(j_num, 0)] = 1\n",
    "                    continue\n",
    "                for k_r in range(rollMax[j_num]):\n",
    "                    idx = self.get_pre_sum_idx(j_num, k_r)\n",
    "                    if k_r == 0:\n",
    "                        rig_start_idx = self.get_pre_sum_idx(j_num + 1, 0)\n",
    "                        for l_idx in range(idx):\n",
    "                            dp_tmp[idx] += dp[l_idx] % M\n",
    "                        for r_idx in range(rig_start_idx, self.pre_sum[-1]):\n",
    "                            dp_tmp[idx] += dp[r_idx] % M\n",
    "                        dp_tmp[idx] %= M\n",
    "                    else:\n",
    "                        dp_tmp[idx] = dp[idx - 1]\n",
    "            dp = dp_tmp\n",
    "        total_sum = int(sum(dp) % M)\n",
    "        return total_sum\n",
    "\n",
    "    def get_pre_sum_idx(self, num, idx):\n",
    "        if num == 0:\n",
    "            return idx\n",
    "        return self.pre_sum[num - 1] + idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        dp = [[1] + [0] * (mx-1) for mx in rollMax]\n",
    "        for _ in range(n-1):\n",
    "            tmp = [[0] * mx for mx in rollMax]\n",
    "            for i in range(6):\n",
    "                tmp[i][0] = sum(sum(dp[j]) % MOD for j in range(6) if j != i) % MOD\n",
    "                for k in range(1, rollMax[i]):\n",
    "                    tmp[i][k] = dp[i][k-1]\n",
    "            dp = tmp\n",
    "        return sum(sum(row) % MOD for row in dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0] * 6 for _ in range(n)]\n",
    "        dp[0] = [1] * 6\n",
    "        s = [0] * n\n",
    "        s[0] = 6\n",
    "\n",
    "        # for i in range(1, n):\n",
    "        #     for j, back in enumerate(rollMax):\n",
    "        #         res = s[i - 1]\n",
    "        #         if i - back> 0:\n",
    "        #             res -= s[i-back-1] - dp[i-back-1][j]\n",
    "        #         elif i == back:\n",
    "        #             res -= 1\n",
    "        #         dp[i][j] = res % MOD\n",
    "        #     s[i] = sum(dp[i]) % MOD\n",
    "        for i in range(1, n):\n",
    "            dp[i] = [sum(dp[i-1])] * 6\n",
    "            for j, back in enumerate(rollMax):\n",
    "                if i - back > 0:\n",
    "                    dp[i][j] -= sum(dp[i-back-1]) - dp[i-back-1][j]\n",
    "                elif i - back == 0:\n",
    "                    dp[i][j] -= 1\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        # print(dp)\n",
    "        # return s[i] % MOD\n",
    "        return sum(dp[-1]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        # https://leetcode.cn/problems/dice-roll-simulation/solutions/492200/ni-bi-dong-chao-jian-dan-dong-tai-gui-hua-fu-za-du/\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0] * 6 for _ in range(n)]\n",
    "        dp[0] = [1] * 6\n",
    "        for i in range(1, n):\n",
    "            dp[i] = [sum(dp[i-1])] * 6\n",
    "            for j, back in enumerate(rollMax):\n",
    "                if i - back > 0:\n",
    "                    dp[i][j] -= sum(dp[i-back-1]) - dp[i-back-1][j]\n",
    "                    # 为什么不要这句？ \n",
    "                    # dp[i][j] -= dp[i-back][j]\n",
    "                elif i - back == 0:\n",
    "                    dp[i][j] -= 1\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        # print(dp)\n",
    "        # return s[i] % MOD\n",
    "        return sum(dp[-1]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [[0] * 6 for _ in range(n)]\n",
    "        f[0] = [1] * 6\n",
    "        s = [0] * n\n",
    "        s[0] = sum(f[0])\n",
    "        for i in range(1, n):\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                res = s[i - 1]\n",
    "                if i > mx: \n",
    "                    res -= s[i - mx - 1] - f[i - mx - 1][j]\n",
    "                elif i == mx: \n",
    "                    res -= 1\n",
    "                f[i][j] = res % MOD\n",
    "            s[i] = sum(f[i]) % MOD\n",
    "        return s[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 1e9 + 7\n",
    "        perms = [[0] * 6 for i in range(n+1)]\n",
    "        for i in range(6):\n",
    "            perms[1][i] = 1\n",
    "        # print(perms)\n",
    "        for nn in range(2, n+1):\n",
    "            # print('nn:', nn)\n",
    "            for i in range(6):\n",
    "                # print('i:', i)\n",
    "                for j in range(1,rollMax[i]+1):\n",
    "                    if nn - j > 0:\n",
    "                        # print('nn:', nn, 'j:', j)\n",
    "                        for k in range(6):\n",
    "                            if k != i:\n",
    "                                # print('k:', k, 'perms[%d][%d]:'%(nn-j, k), perms[nn-j][k])\n",
    "                                perms[nn][i] = (perms[nn][i] + perms[nn-j][k]) % MOD\n",
    "                    elif nn - j == 0:\n",
    "                        perms[nn][i] = (perms[nn][i] + 1) % MOD\n",
    "                # print('perms[%d][%d]:'%(nn, i), perms[nn][i])\n",
    "            # print('perms[%d]:'%nn, perms[nn])\n",
    "        s = 0\n",
    "        for i in perms[n]:\n",
    "            s = (s + i) % MOD\n",
    "        return int(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        Mod=10**9+7\n",
    "        dp=[[0 for _ in range(7)] for _ in range(n+1)]\n",
    "        for j in range(1,7):\n",
    "            dp[1][j]=1\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,7):\n",
    "                ans=sum(dp[i-1])%Mod\n",
    "                idx=i-1-rollMax[j-1]\n",
    "                if idx>=1:\n",
    "                    ans=(ans+Mod-sum(dp[idx])+dp[idx][j])%Mod\n",
    "                elif idx==0:\n",
    "                    ans=(ans-1)%Mod\n",
    "                dp[i][j]=ans%Mod\n",
    "        return sum(dp[n])%Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(rollMax)  # 6\n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        f[0] = [1] * m\n",
    "        s = [0] * n\n",
    "        s[0] = m\n",
    "        for i in range(1, n):\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                res = s[i - 1]\n",
    "                if i > mx: res -= s[i - mx - 1] - f[i - mx - 1][j]\n",
    "                elif i == mx: res -= 1\n",
    "                f[i][j] = res % MOD\n",
    "            s[i] = sum(f[i]) % MOD\n",
    "        return s[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "\n",
    "        # 6面骰子投n次，得到不同点数序列的数量， 限制：连续投掷出i的次数不能超过rollMax[i]\n",
    "\n",
    "        # 1. 递归\n",
    "        # 投骰子的情况：如果和上一个骰子值相同，x连续出现次数不超过rollMax[x];\n",
    "        # 如果不同，重置连续出现的次数为1\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # @cache\n",
    "        # def dfs(i: int, last: int, left: int) -> int: # 剩余投掷次数i,上一个骰子值last, last剩余连续出现次数 left\n",
    "        #     if i == 0: return 1\n",
    "        #     res = 0\n",
    "        #     for j, mx in enumerate(rollMax):\n",
    "        #         if j != last: res += dfs(i - 1, j, mx - 1)\n",
    "        #         elif left: res += dfs(i - 1, j, left - 1)\n",
    "        #     return res % MOD \n",
    "        # return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD\n",
    "\n",
    "        # 2. 递推：\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(rollMax) \n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        f[0] = [1] * m \n",
    "        s = [0] * n \n",
    "        s[0] = m \n",
    "        for i in range(1, n):\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                res = s[i - 1]\n",
    "                if i > mx: res -= s[i - mx - 1] - f[i - mx - 1][j]\n",
    "                elif i == mx: res -= 1\n",
    "                f[i][j] = res % MOD \n",
    "            s[i] = sum(f[i]) % MOD \n",
    "        return s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        # dp[i][j][k] ->\n",
    "        #    i = # has rolled\n",
    "        #    j = num_last_time\n",
    "        #    k = j_occurs_repeated\n",
    "        dp = [[[0]*max(rollMax) for _ in range(6)] for _ in range(n+1)]\n",
    "        for i in range(6):\n",
    "            dp[0][i][0] = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(6):\n",
    "                # dp[i][j][0]\n",
    "                for j2 in range(6):\n",
    "                    if j2 != j:\n",
    "                        dp[i][j][0] += sum(dp[i-1][j2]) % (1000000007)\n",
    "\n",
    "                # dp[i][j][k>1]\n",
    "                for k in range(1, rollMax[j]):\n",
    "                    dp[i][j][k] = dp[i-1][j][k-1]\n",
    "        return sum(sum(dp[n-1][j]) for j in range(6)) % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(rollMax)  # 6\n",
    "        f = [[[0] * mx for mx in rollMax] for _ in range(n)]\n",
    "        f[0] = [[1] * mx for mx in rollMax]\n",
    "        for i in range(1, n):\n",
    "            for last, mx in enumerate(rollMax):\n",
    "                for left in range(mx):\n",
    "                    res = 0\n",
    "                    for j in range(m):\n",
    "                        if j != last:\n",
    "                            res += f[i - 1][j][-1]\n",
    "                        elif left:\n",
    "                            res += f[i - 1][j][left - 1]\n",
    "                    f[i][last][left] = res % MOD\n",
    "        return sum(f[-1][j][-1] for j in range(m)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        #要投n次骰子\n",
    "        \"\"\"\n",
    "        cur_ope: 枚举这次掷骰子是 几\n",
    "        son_pro: 掷 i 次骰子的序列数\n",
    "        next_son_pro: 掷 i - 1 次骰子的序列数\n",
    "        \"\"\"\n",
    "        # #definition: 掷 i 次骰子的序列数\n",
    "        # @cache\n",
    "        # def dfs(i: int, last: int, cnt: int ) -> int:\n",
    "        #     if i == 0:\n",
    "        #         return 1\n",
    "        #     #val_return:\n",
    "        #     res = 0\n",
    "        #     #where\n",
    "        #     for j, x in enumerate(rollMax):\n",
    "        #         if j != last:\n",
    "        #             res = (res + dfs(i - 1, j, x - 1)) % mod\n",
    "        #         else:\n",
    "        #             if cnt > 0:\n",
    "        #                 res = (res + dfs(i - 1, j, cnt - 1)) % mod\n",
    "        #     return res\n",
    "        # ans = 0\n",
    "        # for i, x in enumerate(rollMax):\n",
    "        #     #entrance\n",
    "        #     ans = (ans + dfs(n - 1, i, x - 1)) % mod\n",
    "        # return ans\n",
    "        \"\"\"\n",
    "        dfs -> f\n",
    "        where -> for\n",
    "        boundary -> val_init\n",
    "        \"\"\"\n",
    "        f = [[[0] * x for x in rollMax] for _ in range(n)]\n",
    "        f[0] = [[1] * x for x in rollMax]\n",
    "        #1\n",
    "        for i in range(1, n):\n",
    "            #2\n",
    "            for last, x in enumerate(rollMax):\n",
    "                #3\n",
    "                for cnt in range(x):\n",
    "                    res = 0\n",
    "                    for j, mx in enumerate(rollMax):\n",
    "                        if j != last:\n",
    "                            res = (res + f[i - 1][j][mx - 1]) % mod\n",
    "                        else:\n",
    "                            if cnt > 0:\n",
    "                                res = (res + f[i - 1][j][cnt - 1]) % mod\n",
    "                    f[i][last][cnt] = res\n",
    "        ans = 0\n",
    "        for i, x in enumerate(rollMax):\n",
    "            ans = (ans + f[n - 1][i][x - 1]) %mod\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #i:剩余掷骰子的次数\n",
    "        #last_roll：上一次掷骰子的点数\n",
    "        #left：last的剩余连续出现次数\n",
    "        MOD=10**9+7\n",
    "        #f[剩余掷骰子的次数i][上次掷骰子的点数j][上次掷骰子的点数j剩余连续出现次数left]\n",
    "        f = [[[0] * max_roll for max_roll in rollMax] for _ in range(n)]\n",
    "\n",
    "        f[n-1]=[[1]*max_roll for max_roll in rollMax]     \n",
    "        for i in reversed(range(0,n-1)):\n",
    "            for last_roll,max_roll in enumerate(rollMax):\n",
    "                for left_roll in range(max_roll):\n",
    "                    res=0\n",
    "                    for j in range(6):\n",
    "                        if j==last_roll and left_roll>0:\n",
    "                            res+=f[i+1][j][left_roll-1]\n",
    "                        if j!=last_roll:\n",
    "                            res+=f[i+1][j][rollMax[j]-1]\n",
    "                    f[i][last_roll][left_roll]=res%MOD\n",
    "        \n",
    "\n",
    "        return sum(f[0][j][rollMax[j]-1] for j in range(6))%MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        #要投n次骰子\n",
    "        \"\"\"\n",
    "        cur_ope: 枚举这次掷骰子是 几\n",
    "        son_pro: 掷 i 次骰子的序列数\n",
    "        next_son_pro: 掷 i - 1 次骰子的序列数\n",
    "        \"\"\"\n",
    "        # #definition: 掷 i 次骰子的序列数\n",
    "        # @cache\n",
    "        # def dfs(i: int, last: int, cnt: int ) -> int:\n",
    "        #     if i == 0:\n",
    "        #         return 1\n",
    "        #     #val_return:\n",
    "        #     res = 0\n",
    "        #     #where\n",
    "        #     for j, x in enumerate(rollMax):\n",
    "        #         if j != last:\n",
    "        #             res = (res + dfs(i - 1, j, x - 1)) % mod\n",
    "        #         else:\n",
    "        #             if cnt > 0:\n",
    "        #                 res = (res + dfs(i - 1, j, cnt - 1)) % mod\n",
    "        #     return res\n",
    "        # ans = 0\n",
    "        # for i, x in enumerate(rollMax):\n",
    "        #     #entrance\n",
    "        #     ans = (ans + dfs(n - 1, i, x - 1)) % mod\n",
    "        # return ans\n",
    "        \"\"\"\n",
    "        dfs -> f\n",
    "        where -> for\n",
    "        boundary -> val_init\n",
    "        \"\"\"\n",
    "        f = [[[0] * x for x in rollMax] for _ in range(n)]\n",
    "        f[0] = [[1] * x for x in rollMax]\n",
    "        #1\n",
    "        for i in range(1, n):\n",
    "            #2\n",
    "            for last, x in enumerate(rollMax):\n",
    "                #3\n",
    "                for cnt in range(x):\n",
    "                    res = 0\n",
    "                    for j in range(6):\n",
    "                        if j != last:\n",
    "                            res = (res + f[i - 1][j][-1]) % mod\n",
    "                        else:\n",
    "                            if cnt > 0:\n",
    "                                res = (res + f[i - 1][j][cnt - 1]) % mod\n",
    "                    f[i][last][cnt] = res\n",
    "        ans = 0\n",
    "        for i, x in enumerate(rollMax):\n",
    "            ans = (ans + f[n - 1][i][x - 1]) %mod\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #i:剩余掷骰子的次数\n",
    "        #last_roll：上一次掷骰子的点数\n",
    "        #left：last的剩余连续出现次数\n",
    "        MOD=10**9+7\n",
    "        #f[剩余掷骰子的次数i][上次掷骰子的点数j][上次掷骰子的点数j剩余连续出现次数left]\n",
    "        f = [[[0] * max_roll for max_roll in rollMax] for _ in range(n)]\n",
    "\n",
    "        f[n-1]=[[1]*max_roll for max_roll in rollMax]     \n",
    "        for i in reversed(range(0,n-1)):\n",
    "            for last_roll,max_roll in enumerate(rollMax):\n",
    "                for left_roll in range(max_roll):\n",
    "                    res=0\n",
    "                    for j in range(6):\n",
    "                        if j==last_roll and left_roll>0:\n",
    "                            res+=f[i+1][j][left_roll-1]\n",
    "                        if j!=last_roll:\n",
    "                            res+=f[i+1][j][rollMax[j]-1]\n",
    "                    f[i][last_roll][left_roll]=res%MOD\n",
    "        \n",
    "\n",
    "        return sum(f[0][j][rollMax[j]-1] for j in range(6))%MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #i:剩余掷骰子的次数\n",
    "        #last_roll：上一次掷骰子的点数\n",
    "        #left：last的剩余连续出现次数\n",
    "        MOD=10**9+7\n",
    "        #f[已经掷骰子n][掷n+1骰子的点数j][掷n+1骰子后，点数j可以出现的次数]\n",
    "        f=[[[0]*max_roll for max_roll in rollMax] for _ in range(n)]\n",
    "        f[n-1]=[[1]*max_roll for max_roll in rollMax]\n",
    "        \n",
    "        for i in reversed(range(0,n-1)):\n",
    "            for last_roll,max_roll in enumerate(rollMax):\n",
    "                for left_roll in range(max_roll):\n",
    "                    res=0\n",
    "                    for current_roll in range(6):\n",
    "                        if current_roll==last_roll and left_roll>0:\n",
    "                            res+=f[i+1][current_roll][left_roll-1]\n",
    "                        if current_roll!=last_roll:\n",
    "                            res+=f[i+1][current_roll][rollMax[current_roll]-1]\n",
    "                    f[i][last_roll][left_roll]=res%MOD\n",
    "        \n",
    "        return sum(f[0][j][rollMax[j]-1] for j in range(6))%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i][j][k] represents the number of ways to roll the dice with i times, rolled j and has consequent rolling j k times.\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        maxrolltimes = max(rollMax)\n",
    "        dp = [[[0 for _ in range(maxrolltimes + 1)]  for _ in range(6)]  for _ in range(n + 1)]\n",
    "        for i in range(6):\n",
    "            dp[1][i][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(6):\n",
    "                for k in range(1, rollMax[j] + 1):\n",
    "                    for p in range(6):\n",
    "                        if p != j:\n",
    "                            dp[i][p][1] = (dp[i][p][1] + dp[i - 1][j][k]) % mod\n",
    "                        elif k + 1 <= rollMax[j]:\n",
    "                            dp[i][p][k + 1] = (dp[i][p][k + 1] + dp[i - 1][j][k]) % mod\n",
    "        res = 0\n",
    "        for i in range(6):\n",
    "            for j in range(1, rollMax[i] + 1):\n",
    "                res = (res + dp[n][i][j]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        原问题：\n",
    "        在连续投掷数字 i 的数字不超过 rollMax[i] 的约束下，\n",
    "        投掷 n 次骰子可得到的不同点数序列的个数。\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        # dp[i][j][k]: 表示已经完成了 i 次投掷，第 i 次投掷的是 j，\n",
    "        #              且已经连续投掷了 k 次 j 的合法序列数量\n",
    "        dp = [[[0] * 16 for _ in range(6)] for _ in range(n + 1)]\n",
    "        for j in range(6):\n",
    "            dp[1][j][1] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(6):\n",
    "                for k in range(1, rollMax[j] + 1):\n",
    "                    for p in range(6):\n",
    "                        if p != j:\n",
    "                            dp[i][p][1] = (\n",
    "                                dp[i][p][1] + dp[i - 1][j][k]) % MOD\n",
    "                        elif k + 1 <= rollMax[j]:\n",
    "                            dp[i][p][k + 1] = (\n",
    "                                dp[i][p][k + 1] + dp[i - 1][j][k]) % MOD\n",
    "\n",
    "        res = 0\n",
    "        for j in range(6):\n",
    "            for k in range(1, rollMax[j] + 1):\n",
    "                res = (res + dp[n][j][k]) % MOD\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        dp = [[[0] * 17 for _ in range(7)] for _ in range(n+1)]\n",
    "        mod = 1000000007\n",
    "        for i in range(1,7):\n",
    "            dp[1][i][1] = 1\n",
    "            dp[1][i][-1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,7):\n",
    "                for k in range(1,7):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][-1]) % mod\n",
    "                dp[i][j][-1] = dp[i][j][1]\n",
    "                for k in range(2,rollMax[j-1]+1):\n",
    "                    dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1]) % mod\n",
    "                    dp[i][j][-1] = (dp[i][j][-1] + dp[i][j][k]) % mod\n",
    "        ans = 0\n",
    "        for i in range(1,7):\n",
    "            ans = (ans + dp[n][i][-1]) % mod\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.dieSimulator(2,[1,1,2,2,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        # dp[i][j][k] 表示 第i轮点数为j并且连续k个j时，不同点数序列个数\n",
    "        # 例如 1235666 第7轮点数为6并且3个6\n",
    "        # 其中dp[i][j][-1] 表示第i轮点数为j时连续k(1<=k<=rollMax[j])个j的总和\n",
    "        dp = [[[0] * 17 for _ in range(7)] for _ in range(n+1)]\n",
    "        mod = 1000000007\n",
    "        for i in range(1,7):\n",
    "            dp[1][i][1] = 1\n",
    "            dp[1][i][-1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,7):\n",
    "                # 第i轮只有连续1个j的情况\n",
    "                for k in range(1,7):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][-1]) % mod\n",
    "                dp[i][j][-1] = dp[i][j][1]\n",
    "                # 第i轮连续多个j时的情况\n",
    "                for k in range(2,rollMax[j-1]+1):\n",
    "                    dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1]) % mod\n",
    "                    dp[i][j][-1] = (dp[i][j][-1] + dp[i][j][k]) % mod\n",
    "        ans = 0\n",
    "        for i in range(1,7):\n",
    "            ans = (ans + dp[n][i][-1]) % mod\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.dieSimulator(2,[1,1,2,2,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        dp = [[0] * (6) for _ in range(n+1)]\n",
    "        dp[1] = [1, 1, 1, 1, 1, 1]\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(6):\n",
    "                t = sum(dp[i-1])\n",
    "                if i > rollMax[j]:\n",
    "                    if rollMax[j] + 1 == i:\n",
    "                        t = t - 1\n",
    "                    else:\n",
    "                        t = t - sum(dp[i-rollMax[j] - 1]) + dp[i-rollMax[j] - 1][j]\n",
    "                dp[i][j] = t\n",
    "        return (sum(dp[n]) % 1000000007)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        dp = [[[0] * rollMax[i] for i in range(6)] for _ in range(n)]\r\n",
    "        for i in range(6):\r\n",
    "            dp[0][i][0] = 1\r\n",
    "        tot = 6\r\n",
    "        for i in range(1, n):\r\n",
    "            cur = 0\r\n",
    "            for j in range(6):\r\n",
    "                for k in range(rollMax[j]):\r\n",
    "                    if k == 0:\r\n",
    "                        dp[i][j][k] = tot - sum(dp[i - 1][j])\r\n",
    "                    else:\r\n",
    "                        dp[i][j][k] = dp[i - 1][j][k - 1]\r\n",
    "                    cur += dp[i][j][k]\r\n",
    "            tot = cur\r\n",
    "        return tot % mod\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        f=[[0]*8 for _ in range(n+1)]\n",
    "        for i in range(1,7): f[1][i]=1\n",
    "        f[1][7]=6\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            \n",
    "            for j in range(1,7):\n",
    "                f[i][j]=f[i-1][7]\n",
    "                k=i-rollMax[j-1]\n",
    "                if k==1:\n",
    "                    f[i][j] -=1\n",
    "                elif k>1:\n",
    "                    f[i][j] -=f[k-1][7]-f[k-1][j]\n",
    "\n",
    "                f[i][7] +=f[i][j]\n",
    "            \n",
    "        return f[n][7]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i:int, last:int, left:int) -> int:\n",
    "            if i == 0: return 1\n",
    "            res = 0\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                if j != last: res += dfs(i - 1, j, mx - 1)\n",
    "                elif left: res += dfs(i - 1, j, left - 1)\n",
    "            return res % MOD\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, pre, cnt):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for i in range(1, 7):\n",
    "                if i == pre and cnt + 1 > rollMax[i - 1]:\n",
    "                    continue\n",
    "                res += dfs(idx + 1, i, 1 if i != pre else cnt + 1)\n",
    "                res %= kmod\n",
    "            return res\n",
    "        ans = dfs(0, -1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        # 回溯的思想：如果不做限制的话：\n",
    "        # 就是6 ** n，也就是一颗6叉树一样的东西，如果连续超过了rollmax，那么回溯\n",
    "        @cache\n",
    "        def dfs(i, last, left):\n",
    "            # i:how many times can we roll\n",
    "            # j:result of last roll\n",
    "            # left:comes form lowmax\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                # means this time we rolled j\n",
    "                if j != last:\n",
    "                    res += dfs(i - 1, j, mx - 1)\n",
    "                elif left > 0:\n",
    "                    res += dfs(i - 1, j, left - 1)\n",
    "                # if left == 0: means this time, we don't have room for duplicate so res is still 0\n",
    "            return res % MOD\n",
    "\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = int(1E9 + 7)\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(remains_cnt: int, last_val: int, left: int) -> int:\n",
    "            if remains_cnt == 0:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "            for v, mx in enumerate(rollMax):\n",
    "                if v != last_val:\n",
    "                    ans += dfs(remains_cnt - 1, v, mx - 1)\n",
    "                elif left > 0:\n",
    "                    ans += dfs(remains_cnt - 1, v, left - 1)\n",
    "            return ans % MOD\n",
    "\n",
    "        return sum([dfs(n - 1, v, mx - 1) for v, mx in enumerate(rollMax)]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD= 10**9+7\n",
    "\n",
    "        # 剩余掷骰子的次数，用 i 表示；\n",
    "        # 上一个骰子值，用 last 表示；\n",
    "        # last的剩余连续出现次数，用 left 表示。\n",
    "        # 倒序遍历\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,last,left):\n",
    "            if i == 0:#i递归到 n=0时结束，返回1，表示找到了一个合法骰子序列。\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j,mx in enumerate(rollMax):\n",
    "                if j == last:\n",
    "                    if  left:\n",
    "                        res += dfs(i-1,j,left-1)\n",
    "                else:\n",
    "                    res += dfs(i-1,j,mx-1)\n",
    "            return res%MOD\n",
    "        #每个从最后一个开始\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD\n",
    "                    \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #i:剩余掷骰子的次数\n",
    "        #last：上一次掷骰子的点数\n",
    "        #left：last的剩余连续出现次数\n",
    "        MOD=10**9+7\n",
    "        @cache\n",
    "        def dfs(i,last,left):\n",
    "            if i==0:\n",
    "                return 1\n",
    "            res=0\n",
    "            for j,n_max in enumerate(rollMax):\n",
    "                if j!=last:\n",
    "                    res+=dfs(i-1,j,n_max-1)\n",
    "                elif left>0:\n",
    "                    res+=dfs(i-1,j,left-1)\n",
    "            return res%MOD\n",
    "        ans=sum(dfs(n-1,j,n_max-1) for j, n_max in enumerate(rollMax))%MOD\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        #要投n次骰子\n",
    "        \"\"\"\n",
    "        cur_ope: 枚举这次掷骰子是 几\n",
    "        son_pro: 掷 i 次骰子的序列数\n",
    "        next_son_pro: 掷 i - 1 次骰子的序列数\n",
    "        \"\"\"\n",
    "        #definition: 掷 i 次骰子的序列数\n",
    "        @cache\n",
    "        def dfs(i: int, last: int, cnt: int ) -> int:\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            #val_return:\n",
    "            res = 0\n",
    "            #where\n",
    "            for j, x in enumerate(rollMax):\n",
    "                if j != last:\n",
    "                    res = (res + dfs(i - 1, j, x - 1)) % mod\n",
    "                else:\n",
    "                    if cnt > 0:\n",
    "                        res = (res + dfs(i - 1, j, cnt - 1)) % mod\n",
    "            return res\n",
    "        ans = 0\n",
    "        for i, x in enumerate(rollMax):\n",
    "            #entrance\n",
    "            ans = (ans + dfs(n - 1, i, x - 1)) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, last: int, left: int) -> int:\n",
    "            if i == 0: return 1\n",
    "            res = 0\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                if j != last: res += dfs(i - 1, j, mx - 1)\n",
    "                elif left: res += dfs(i - 1, j, left - 1)\n",
    "            return res % MOD\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, last: int, left: int) -> int:\n",
    "            if i == 0: return 1\n",
    "            res = 0\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                if j != last: res += dfs(i - 1, j, mx - 1)\n",
    "                elif left: res += dfs(i - 1, j, left - 1)\n",
    "            return res % MOD\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, last, left):\n",
    "            # i 代表还剩几次投掷次数，j 代表上次投掷了多少点，left代表还剩几次达到rollmax\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                if j == last and left > 0:\n",
    "                    res += dfs(i - 1, j, left - 1)\n",
    "                elif j != last:\n",
    "                    res += dfs(i - 1, j, mx - 1)\n",
    "\n",
    "            return res % MOD\n",
    "\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, last: int, left: int) -> int:\n",
    "            if i == 0: return 1\n",
    "            res = 0\n",
    "            for j, mx in enumerate(rollMax):\n",
    "                if j != last: res += dfs(i - 1, j, mx - 1)\n",
    "                elif left: res += dfs(i - 1, j, left - 1)\n",
    "            return res % MOD\n",
    "        return sum(dfs(n - 1, j, mx - 1) for j, mx in enumerate(rollMax)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution(object):\n",
    "    def dieSimulator(self, n, rollMax):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type rollMax: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def f(i,last,left):\n",
    "            if i==0: \n",
    "                return 1\n",
    "            result = 0\n",
    "            for j,res in enumerate(rollMax):\n",
    "                if j!=last:\n",
    "                    result+=f(i-1,j,res-1)\n",
    "                elif left!=0:\n",
    "                    result+=f(i-1,j,left-1)\n",
    "            return result % MOD\n",
    "        return sum(f(n-1,j,res-1) for j,res in enumerate(rollMax) )%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\r\n",
    "        Q = 10 ** 9 + 7\r\n",
    "        # i 第几次摇\r\n",
    "        # num 上一次摇出什么数字\r\n",
    "        # time 已经连续几次相同数字了\r\n",
    "        @cache\r\n",
    "        def dfs(i, num, time): \r\n",
    "            if i == n:\r\n",
    "                return 1\r\n",
    "            res = sum(dfs(i + 1, dice, 1) for dice in range(6) if dice != num) % Q # 摇出其他数字\r\n",
    "            if time < rollMax[num]: # 如果还未达到最大限制，可以摇出相同数字\r\n",
    "                res += dfs(i + 1, num, time + 1)\r\n",
    "            return res % Q\r\n",
    "        return sum(dfs(1, num, 1) for num in range(6)) % Q\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #需要记录前置数字及其连续长度\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i==0: return 1\n",
    "            res=0\n",
    "            num,cnt=pre[0],pre[1]\n",
    "            for j in range(1,7):\n",
    "                if j!=num:\n",
    "                    res+=dfs(i-1,(j,1))\n",
    "                else:\n",
    "                    if cnt<rollMax[j-1]:\n",
    "                        res+=dfs(i-1,(j,cnt+1))\n",
    "            return res%MOD\n",
    "        return dfs(n,(0,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #需要记录前置数字及其连续长度\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i==0: return 1\n",
    "            res=0\n",
    "            num,cnt=pre[0],pre[1]\n",
    "            for j in range(1,7):\n",
    "                if j!=num:\n",
    "                    res+=dfs(i-1,(j,1))\n",
    "                else:\n",
    "                    if cnt<rollMax[j-1]:\n",
    "                        res+=dfs(i-1,(j,cnt+1))\n",
    "            return res%MOD\n",
    "        return dfs(n,(0,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, pre, left):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            \n",
    "            ans = 0\n",
    "            for j in range(6):\n",
    "                if j == pre:\n",
    "                    if left > 0:\n",
    "                        ans += dfs(i+1, j, left-1)\n",
    "                else:\n",
    "                    ans += dfs(i+1, j, rollMax[j]-1)\n",
    "            return ans % MOD\n",
    "        \n",
    "        return dfs(0, -1, 0) % MOD\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #经典记忆化搜索\n",
    "        #需要记录前置数字及其连续长度\n",
    "        @cache\n",
    "        def dfs(i,pre,cnt):\n",
    "            if i==0: return 1\n",
    "            res=0\n",
    "            for j in range(1,7):\n",
    "                if j!=pre:\n",
    "                    res+=dfs(i-1,j,1)\n",
    "                else:\n",
    "                    if cnt<rollMax[j-1]:\n",
    "                        res+=dfs(i-1,pre,cnt+1)\n",
    "            return res%MOD\n",
    "        return dfs(n,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod = 1000000007\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, left: int) -> int: # dfs(i, j, left) 代表第i次投出了j此时j的剩余次数为left的答案\n",
    "            if i <= 0:\n",
    "                return 0\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            # 枚举前一个\n",
    "            for k in range(1, 7):\n",
    "                if k != j:\n",
    "                    res += dfs(i - 1, k, rollMax[k - 1] - 1)\n",
    "                elif left > 0:\n",
    "                    res += dfs(i - 1, j, left - 1)\n",
    "            return res % mod\n",
    "        ans = 0\n",
    "        for i in range(1, 7):\n",
    "            ans += dfs(n, i, rollMax[i - 1] - 1)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\r\n",
    "        @cache\r\n",
    "        def dfs(n, pre, k):\r\n",
    "            if n == 0:\r\n",
    "                return 1\r\n",
    "            res = 0\r\n",
    "            for i in range(6):\r\n",
    "                if i == pre and k == rollMax[i]:\r\n",
    "                    continue\r\n",
    "                res = (res + dfs(n - 1, i, k + 1 if i == pre else 1))%(10**9 + 7)\r\n",
    "            return res\r\n",
    "        return dfs(n, -1, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, last, left):\n",
    "            if i <= 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(6):\n",
    "                if j == last and left > 0:\n",
    "                    ans += dfs(i-1, j, left-1)\n",
    "                elif j != last:\n",
    "                    ans += dfs(i-1, j, rollMax[j] -1)\n",
    "            return ans % (10**9+7)\n",
    "        return sum(dfs(n-1, i, rollMax[i]-1) for i in range(6)) % (10**9+7)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\r\n",
    "        @cache\r\n",
    "        def dfs(n, pre, k):\r\n",
    "            if n == 0:\r\n",
    "                return 1\r\n",
    "            res = 0\r\n",
    "            for i in range(6):\r\n",
    "                if i == pre and k == rollMax[i]:\r\n",
    "                    continue\r\n",
    "                res = (res + dfs(n - 1, i, k + 1 if i == pre else 1)) % (10**9 + 7)\r\n",
    "            return res\r\n",
    "        return dfs(n, -1, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\r\n",
    "        @cache\r\n",
    "        def dfs(n, pre, k):\r\n",
    "            if n == 0:\r\n",
    "                return 1\r\n",
    "            res = 0\r\n",
    "            for i in range(6):\r\n",
    "                if i == pre and k == rollMax[i]:\r\n",
    "                    continue\r\n",
    "                res = (res + dfs(n - 1, i, k + 1 if i == pre else 1)) % (10**9 + 7)\r\n",
    "            return res\r\n",
    "        return dfs(n, -1, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        #需要记录前置数字及其连续长度\n",
    "        @cache\n",
    "        def dfs(i,pre,cnt):\n",
    "            if i==0: return 1\n",
    "            res=0\n",
    "            for j in range(1,7):\n",
    "                if j!=pre:\n",
    "                    res+=dfs(i-1,j,1)\n",
    "                else:\n",
    "                    if cnt<rollMax[j-1]:\n",
    "                        res+=dfs(i-1,pre,cnt+1)\n",
    "            return res%MOD\n",
    "        return dfs(n,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(i,j,k):\n",
    "            if i<=0:\n",
    "                if rollMax[j]>=k:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            res=0\n",
    "            for m in range(6):\n",
    "                if m==j:\n",
    "                    if rollMax[m]<=k:\n",
    "                        continue\n",
    "                    else:\n",
    "                        res+=dfs(i-1,j,k+1)\n",
    "                else:\n",
    "                    res+=dfs(i-1,m,1)\n",
    "            return res%mod\n",
    "        return sum(dfs(n-1,j,1) for j in range(6))%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\r\n",
    "        @cache\r\n",
    "        def dfs(n, pre, k):\r\n",
    "            if n == 0:\r\n",
    "                return 1\r\n",
    "            res = 0\r\n",
    "            for i in range(6):\r\n",
    "                if i == pre and k == rollMax[i]:\r\n",
    "                    continue\r\n",
    "                res = (res + dfs(n - 1, i, k + 1 if i == pre else 1)) % (10**9 + 7)\r\n",
    "            return res\r\n",
    "        return dfs(n, -1, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       \n",
    "       @cache\n",
    "       def dfs(i: int, j: int, k: int) -> int:\n",
    "          if i == n:\n",
    "             return 1\n",
    "          res = 0\n",
    "          for x in range(1, 7):\n",
    "             if x != j:\n",
    "                res += dfs(i + 1, x, rollMax[x - 1] - 1)\n",
    "             elif k:\n",
    "                res += dfs(i + 1, x, k - 1)\n",
    "             res %= MOD\n",
    "          return res\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int, cnt: int) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j in range(6):\n",
    "                if j == pre:\n",
    "                    if cnt == rollMax[j]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        res += dfs(i + 1, j, cnt + 1)\n",
    "                else:\n",
    "                    res += dfs(i + 1, j, 1)\n",
    "            return res % MOD\n",
    "        return dfs(0, -1, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n",
    "\n",
    "        mod = 10**9+7\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, p, c):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(6):\n",
    "                nex_p = j\n",
    "                nex_c = rollMax[j]-1 if j != p else c-1\n",
    "                if nex_c>=0:\n",
    "                    ans += dfs(i+1, nex_p, nex_c)\n",
    "                \n",
    "            return ans % mod \n",
    "        \n",
    "        return dfs(0, -1, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
